package com.dataStructure.队列;

@SuppressWarnings("unchecked")
public class CircleQueue_循环队列<E> {
    private int front;
    private int size;
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;

    public CircleQueue_循环队列() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    public void clear(){
        size = 0;
        front = 0;
        for (int i = 0; i < size; i++) {
            elements[index(i)] = null;
        }
    }

    // 元素的数量
    public int size() {
        return size();
    }

    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 清空
 /*   public void clear() {
        front = 0;
        size = 0;
    }*/

    // 入队
    public void enQueue(E element) {
        ensureCapaity(size + 1);
        //取模运算：模数 % 被模数 = 余数
        //如果模数小于被模数，那么模出来的余数等于模数自己
        //模数一旦等于被模数，余数等于0
        //模数大被模数1，余数为1
        //如此反复循环
        //比如被模数为5，任何模数模它的范围始终在0 1 2 3 4
        //被模数为11，范围为0 1 2 3 4 5 6 7 8 9 10

        /*
        *以下入队的操作就是使用了这个规律，front + size 本来如果不采用循环队列 其值应该就是元素插入的索引位置
        *使用循环队列后，只用模以这个数组的长度，front + size的大小没有超过这个数组的长度的时候，是挨个放进数组后面剩余的位置
        *当front + size的大小超过数组长度了，此时就要从新开始放在数组头了 利用了取模得到的数字，反复循环的特点
        */
        elements[(front + size) % elements.length] = element;
        size ++;
    }

    // 出队
    public E deQueue() {
        E frontElement = elements[front];
        elements[front] = null;

        front = (front+1) % elements.length;
        size --;
        return frontElement;
    }

    //获取队列头元素
    public E front() {
        return elements[front];
    }

    @Override
    public String toString(){
        StringBuilder string = new StringBuilder();
        string.append("capcacity=").append(elements.length)
                .append(" size=").append(size)
                .append(" front=").append(front)
                .append(", [");
        for (int i = 0; i < elements.length; i++) {
            if (i != 0) {
                string.append(", ");
            }

            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }

    //扩容
    private void ensureCapaity(int capaity) {
        int oldCapaity = elements.length;
        if (oldCapaity >= capaity) return;
        //扩容为原数组的1.5倍
        int newCapaity = oldCapaity + (oldCapaity >> 1);
        E[] newElements = (E[]) new Object [newCapaity];
        for (int i = 0; i < size-1; i++) {
            newElements[i] = elements[index(i)];
        }
        elements = newElements;
        System.out.println("beforekuorong:" + oldCapaity + "afterkuorong" + newCapaity);
        //重置front指针 l,,
        front = 0;
    }
     private  int index (int index){
        return (front + index)%elements.length;
    }
}
